Large 3D engineering models like architectural designs, chemical plants and mechanical CAD (computer-aided design) designs are increasingly being deployed in various virtual world applications, such as Second Life™ and Google Earth™ In most engineering models there are a large number of small to medium sized connected components, each having up to a few hundred polygons on average. A subset of a mesh model is a connected component if there exists a path between any two polygons in it, as defined in [SBM01]1. Moreover, this type of models has a number of geometric features that is repeated in various positions, scales and orientations. 1 [SBM01]: D. Shikhare, S. Bhakar and S. P. Mudur. “Compression of Large 3D Engineering Models using Automatic Discovery of Repeating Geometric Features”, Nov. 21-23, 2001, Stuttgart, Germany
Various algorithms have been proposed to compress 3D meshes efficiently since the early 1990s. Early work however mostly concentrates on compressing single connected 3D models with smooth surface and small triangles. For multi-connected 3D models (3D models containing multiple connected components), such as large 3D engineering models, the components are compressed separately. This causes a relatively ineffective compression. In fact, the compression performance can be greatly increased by removing the redundancy between different connected components.
A method for automatically discovering repeating geometric features in large 3D engineering models is proposed in [SBM01]. However, much room is left for more efficient compression of 3D engineering models. E.g., no compression solution is provided that covers transformation information of repeated instances, which is necessary for restoring the original model. Considering the large size of connected components that a 3D engineering model usually has, this kind of information will consume a big amount of storage. Further, if PCA (Principal Component Analysis) of positions of vertices of a component is used, components with same geometry and different connectivity will have the same mean and same orientation axes. The state of the art is not suitable for detecting and/or compressing repeating patterns in various scales. Two components that differ only in scale (i.e. size) are not recognized as repeating features of same equivalence class. Further, it is desirable to achieve a higher compression ratio than described in [SBM01].
[OG00]2 discloses a KD-tree based compression algorithm to encode the means of all connected components of a mesh model. This algorithm subdivides with each iteration a cell into two child cells, and encodes the number of vertices in one of the two child cells. If the parent cell contains p vertices, the number of vertices in one of the child cells can be encoded using log2(p+1) bits with an arithmetic coder. This subdivision is recursively applied, until each non-empty cell is small enough to contain only one vertex and enables a sufficiently precise reconstruction of the vertex position. It is mentioned in [OG00] that the algorithm is most efficient for non-uniform distributions, with regular distribution being the worst case. 2 [OG00]: O. Devillers, P. Gandoin. “Geometric compression for interactive transmission”, in: IEEE Visualization, 2000, pp. 319-326